function ret=init_gnat(lst)
  global mplist;
  mplist=lst;
  mps=[1:length(mplist)];
  ret=generate_gnat(mps);
endfunction

function ret=generate_gnat(mps)
  gnat.size=length(mps);
  if(length(mps)<=getMinSize())
   gnat.points=mps;
   ret=gnat;
   return;
  endif

  gnat.spliting_points=generate_spliting_points(mps);
  gnat.subGnats=generate_subGnats(gnat.spliting_points,mps);
  %[gnat.max_range,gnat.min_range]=comput_range(gnat,mplist);
  ret=gnat;
endfunction

function ret=generate_spliting_points(mps)
 ret=[];
 n1=getSubGnatNumber();
 n2=length(mps);
 d=round(n2/n1);
 for i=1:n1
  k=(i-1)*d;
  ret(end+1)=mps(round(rand*d)+k);
 endfor
endfunction

function ret=generate_subGnats(spliting_points,mps)
 %mps:vector-array of index for points in gnat
 %mplist: cell-array of points structure
 global mplist;
 
 sp={};
 for j=1:length(spliting_points)
   d=spliting_points(j);
   sp{end+1}=mplist{d};
 endfor
 %sp:array of splitting points
   
 nearest_sppoints=[];
 for i=1:length(mps)
  d=mps(i);
  %index of element i in vector-array of points in gnat
  p=mplist{d};
  ret=min_distance(sp,p);
  nearest_sppoints(d)=ret{3};
 endfor
 %nearest_sppoints: vector-array of index of nearest spliting_points in sp
 
 for i=1:length(sp)
  subgnats{i}=[];
  d=spliting_points(i);
  nearest_sppoints(d)=i;
 endfor
 %subgnats{i}: vector-array of index of  points in cluster i
 
 for i=1:length(mps)
  d=mps(i);
  k=nearest_sppoints(d);
  subgnats{k}(end+1)=mps(i);
 endfor
 
 for i=1:length(subgnats)
   subGnats{i}=generate_gnat(subgnats{i});
 endfor

 ret=subGnats;
endfunction

function ret=getMinSize()
 ret=600;
endfunction

function ret=getSubGnatNumber()
 ret=20;
endfunction
